package sort

/*
	k 桶的个数
	平均时间复杂度：O(n*k)
	最好情况：O(n*k)
	最坏情况：O(n*k)
	空间复杂度：O(n+k)
	排序方式：InPlace
	稳定性：稳定
*/

func RadixSort(nums []int) {

	max := nums[0]

	// 获得最大值
	for _, v := range nums {
		if v > max {
			v = max
		}
	}

	// 计算位数
	dig := 0
	if max > 0 {
		for temp := max; temp > 0; temp /= 10 {
			dig++
		}
	} else {
		dig = 1
	}

	mod := 10

	// 开始排序
	for i := 0; i < dig; i++ {
		buckets := make([][]int, 10)
		for i := 0; i < 10; i++ {
			buckets[i] = []int{}
		}

		// 计算位数放入桶中
		for _, v := range nums {
			x := v % mod / (mod / 10)
			buckets[x] = append(buckets[x], v)
		}

		index := 0
		// 按序插入排序插入nums
		for _, b := range buckets {
			for _, v := range b {
				nums[index] = v
				index++
			}
		}

		mod *= 10

	}

}
